package leetcode_201_300;

import com.sun.xml.internal.bind.v2.model.core.ID;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LeeCode_279_timeout {
    public static void main(String[] args) {
        System.out.println(numSquares(13));
        System.out.println(numSquares(12));
    }
    private static int numSquares(int n) {
        double m = Math.pow(n, 0.5);
        int i = 1;
        List<Integer> list = new ArrayList<>();
        while (i <= m){
            list.add(i * i);
            i++;
        }
        return dfs(list, n,list.size() - 1, 0, 0);
    }
    private static int dfs(List<Integer> list,int n, int index, int count, int sum){
        if (sum == n)
            return count;
        if (sum > n || index < 0)
            return -1;
        int num = list.get(index);
        int d1 = dfs(list, n, index, count + 1, sum + num);
        int d2 = dfs(list, n, index - 1, count + 1, sum + num);
        int d3 = dfs(list, n, index - 1, count, sum);
        int a1 = d1 == -1 ? Integer.MAX_VALUE : d1;
        int a2 = d2 == -1 ? Integer.MAX_VALUE : d2;
        int a3 = d3 == -1 ? Integer.MAX_VALUE : d3;
        return Math.min(a1, Math.min(a2, a3));
    }
}
